package hot100;


/*
 * Author：江松
 * Date：2023/4/16 9:46
 *
 三数之和：
 1，利用哈希表快速查询，遍历2个数求得其相反数，如果集合中存在就是答案
 并且根据set特性，是去重的——不行

 题解：优化过程
 1，O(n^3)遍历
 2,排序减少重复，使得a<=b<=c
 3，减少循环次数，a+b+c=0,a+b'+c'=0,b'>b说明c'<c,说明c可以从右往左枚举，这样就成了2重循环
 排序+双指针
 排序后，一重循环枚举所有点，第二重循环枚举两数和=t1的点（经典2数和问题），注意去重
 */

import java.util.*;

public class Main15 {


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>res=new LinkedList<>();
        int n=nums.length;

        Arrays.sort(nums);
        for(int i=0;i<n;++i){
            if(nums[i]>0)return res;
            if(i>0&&nums[i]==nums[i-1])continue;

            int t1=-nums[i];
            int l=i+1,r=n-1;
            while(l<r){
                int t2=nums[l],t3=nums[r];
                if(t2+t3<t1)l++;
                else if(t2+t3>t1)r--;
                else{
                    List<Integer>tmp=new ArrayList<>();
                    tmp.add(-t1);
                    tmp.add(t2);
                    tmp.add(t3);
                    res.add(tmp);
                    l++;r--;
                    while(l<r&&nums[l-1]==nums[l])l++;
                    while(l<r&&nums[r+1]==nums[r])r--;
                }
            }
        }
        return res;
    }
}
